home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 2 / Atari Mega Archive CD - Volume 2.iso / minix / up1510b.tgz / up1510b / src / fs / cache.c < prev    next >
C/C++ Source or Header  |  1990-07-23  |  14KB  |  395 lines
  1. /* The file system maintains a buffer cache to reduce the number of disk
  2.  * accesses needed.  Whenever a read or write to the disk is done, a check is
  3.  * first made to see if the block is in the cache.  This file manages the
  4.  * cache.
  5.  *
  6.  * The entry points into this file are:
  7.  *   get_block:      request to fetch a block for reading or writing from cache
  8.  *   put_block:      return a block previously requested with get_block
  9.  *   alloc_zone:  allocate a new zone (to increase the length of a file)
  10.  *   free_zone:      release a zone (when a file is removed)
  11.  *   rw_block:      read or write a block from the disk itself
  12.  *   invalidate:  remove all the cache blocks on some device
  13.  */
  14.  
  15. #include "fs.h"
  16. #include <minix/com.h>
  17. #include <minix/boot.h>
  18. #include "buf.h"
  19. #include "file.h"
  20. #include "fproc.h"
  21. #include "inode.h"
  22. #include "super.h"
  23.  
  24. /*===========================================================================*
  25.  *                get_block                     *
  26.  *===========================================================================*/
  27. PUBLIC struct buf *get_block(dev, block, only_search)
  28. register dev_t dev;        /* on which device is the block? */
  29. register block_nr block;    /* which block is wanted? */
  30. int only_search;        /* if NO_READ, don't read, else act normal */
  31. {
  32. /* Check to see if the requested block is in the block cache.  If so, return
  33.  * a pointer to it.  If not, evict some other block and fetch it (unless
  34.  * 'only_search' is 1).  All blocks in the cache, whether in use or not,
  35.  * are linked together in a chain, with 'front' pointing to the least recently
  36.  * used block and 'rear' to the most recently used block.  If 'only_search' is
  37.  * 1, the block being requested will be overwritten in its entirety, so it is
  38.  * only necessary to see if it is in the cache; if it is not, any free buffer
  39.  * will do.  It is not necessary to actually read the block in from disk.
  40.  * If 'only_search' is PREFETCH, the block need not be read from the disk,
  41.  * and the device is not to be marked on the block, so callers can tell if
  42.  * the block returned is valid.
  43.  * In addition to the LRU chain, there is also a hash chain to link together
  44.  * blocks whose block numbers end with the same bit strings, for fast lookup.
  45.  */
  46.  
  47.   register struct buf *bp, *prev_ptr;
  48.  
  49.   /* Search the hash chain for (dev, block). */
  50.   if (dev != NO_DEV) {
  51.     /* ??? DEBUG What if dev == NO_DEV ??? */
  52.     bp = buf_hash[block & (NR_BUF_HASH - 1)];
  53.     while (bp != NIL_BUF) {
  54.         if (bp->b_blocknr == block && bp->b_dev == dev) {
  55.             /* Block needed has been found. */
  56.             if (bp->b_count == 0) bufs_in_use++;
  57.             bp->b_count++;    /* record that block is in use */
  58.             return(bp);
  59.         } else {
  60.             /* This block is not the one sought. */
  61.             bp = bp->b_hash; /* move to next block on hash chain */
  62.         }
  63.     }
  64.   }
  65.  
  66.   /* Desired block is not on available chain.  Take oldest block ('front').
  67.    * However, a block that is already in use (b_count != 0) may not be taken.
  68.    */
  69.   if (bufs_in_use == NR_BUFS) panic("All buffers in use", NR_BUFS);
  70.   bp = front;
  71.   while (bp->b_count != 0) {
  72.     bp = bp->b_next;
  73.     if (bp == NIL_BUF) panic("No free buffer", NO_NUM);
  74.   }
  75.   bufs_in_use++;        /* one more buffer in use now */
  76.  
  77.   /* Remove the block that was just taken from its hash chain. */
  78.   prev_ptr = buf_hash[bp->b_blocknr & (NR_BUF_HASH - 1)];
  79.   if (prev_ptr == bp) {
  80.     buf_hash[bp->b_blocknr & (NR_BUF_HASH - 1)] = bp->b_hash;
  81.   } else {
  82.     /* The block just taken is not on the front of its hash chain. */
  83.     while (prev_ptr->b_hash != NIL_BUF)
  84.         if (prev_ptr->b_hash == bp) {
  85.             prev_ptr->b_hash = bp->b_hash;    /* found it */
  86.             break;
  87.         } else {
  88.             prev_ptr = prev_ptr->b_hash;    /* keep looking */
  89.         }
  90.   }
  91.  
  92.   /* If the block taken is dirty, make it clean by writing it to the disk.
  93.    * Avoid hysterisis by flushing all other dirty blocks for the same device.
  94.    */
  95.   if (bp->b_dev != NO_DEV && bp->b_dirt == DIRTY) flushall(bp->b_dev);
  96.  
  97.   /* Fill in block's parameters and add it to the hash chain where it goes. */
  98.   bp->b_dev = dev;        /* fill in device number */
  99.   if (only_search == PREFETCH) bp->b_dev = NO_DEV;
  100.   bp->b_blocknr = block;    /* fill in block number */
  101.   bp->b_count++;        /* record that block is being used */
  102.   bp->b_hash = buf_hash[bp->b_blocknr & (NR_BUF_HASH - 1)];
  103.   buf_hash[bp->b_blocknr & (NR_BUF_HASH - 1)] = bp;    /* add to hash list */
  104.  
  105.   /* Go get the requested block unless searching or prefetching. */
  106.   if (dev != NO_DEV && only_search == NORMAL) rw_block(bp, READING);
  107.   return(bp);            /* return the newly acquired block */
  108. }
  109.  
  110.  
  111. /*===========================================================================*
  112.  *                put_block                     *
  113.  *===========================================================================*/
  114. PUBLIC void put_block(bp, block_type)
  115. register struct buf *bp;    /* pointer to the buffer to be released */
  116. int block_type;            /* INODE_BLOCK, DIRECTORY_BLOCK, or whatever */
  117. {
  118. /* Return a block to the list of available blocks.   Depending on 'block_type'
  119.  * it may be put on the front or rear of the LRU chain.  Blocks that are
  120.  * expected to be needed again shortly (e.g., partially full data blocks)
  121.  * go on the rear; blocks that are unlikely to be needed again shortly
  122.  * (e.g., full data blocks) go on the front.  Blocks whose loss can hurt
  123.  * the integrity of the file system (e.g., inode blocks) are written to
  124.  * disk immediately if they are dirty.  
  125.  */
  126.  
  127.   register struct buf *next_ptr, *prev_ptr;
  128.  
  129.   if (bp == NIL_BUF) return;    /* it is easier to check here than in caller */
  130.  
  131.   /* If block is no longer in use, first remove it from LRU chain. */
  132.   bp->b_count--;        /* there is one use fewer now */
  133.   if (bp->b_count != 0) return;    /* block is still in use */
  134.  
  135.   bufs_in_use--;        /* one fewer block buffers in use */
  136.   next_ptr = bp->b_next;    /* successor on LRU chain */
  137.   prev_ptr = bp->b_prev;    /* predecessor on LRU chain */
  138.   if (prev_ptr != NIL_BUF)
  139.     prev_ptr->b_next = next_ptr;
  140.   else
  141.     front = next_ptr;    /* this block was at front of chain */
  142.  
  143.   if (next_ptr != NIL_BUF)
  144.     next_ptr->b_prev = prev_ptr;
  145.   else
  146.     rear = prev_ptr;    /* this block was at rear of chain */
  147.  
  148.   /* Put this block back on the LRU chain.  If the ONE_SHOT bit is set in
  149.    * 'block_type', the block is not likely to be needed again shortly, so put
  150.    * it on the front of the LRU chain where it will be the first one to be
  151.    * taken when a free buffer is needed later.
  152.    */
  153.   if (block_type & ONE_SHOT) {
  154.     /* Block probably won't be needed quickly. Put it on front of chain.
  155.        * It will be the next block to be evicted from the cache.
  156.        */
  157.     bp->b_prev = NIL_BUF;
  158.     bp->b_next = front;
  159.     if (front == NIL_BUF)
  160.         rear = bp;    /* LRU chain was empty */
  161.     else
  162.         front->b_prev = bp;
  163.     front = bp;
  164.   } else {
  165.     /* Block probably will be needed quickly.  Put it on rear of chain.
  166.        * It will not be evicted from the cache for a long time.
  167.        */
  168.     bp->b_prev = rear;
  169.     bp->b_next = NIL_BUF;
  170.     if (rear == NIL_BUF)
  171.         front = bp;
  172.     else
  173.         rear->b_next = bp;
  174.     rear = bp;
  175.   }
  176.  
  177.   /* Some blocks are so important (e.g., inodes, indirect blocks) that they
  178.    * should be written to the disk immediately to avoid messing up the file
  179.    * system in the event of a crash.
  180.    */
  181.   if ((block_type & WRITE_IMMED) && bp->b_dirt==DIRTY && bp->b_dev != NO_DEV)
  182.     rw_block(bp, WRITING);
  183.  
  184.   /* Super blocks must not be cached, lest mount use cached block. */
  185.   if (block_type == ZUPER_BLOCK) bp->b_dev = NO_DEV;
  186. }
  187.  
  188.  
  189. /*===========================================================================*
  190.  *                alloc_zone                     *
  191.  *===========================================================================*/
  192. PUBLIC zone_nr alloc_zone(dev, z)
  193. dev_t dev;            /* device where zone wanted */
  194. zone_nr z;            /* try to allocate new zone near this one */
  195. {
  196. /* Allocate a new zone on the indicated device and return its number. */
  197.  
  198.   bit_nr b, bit;
  199.   struct super_block *sp;
  200.   int major, minor;
  201.  
  202.   /* Note that the routine alloc_bit() returns 1 for the lowest possible
  203.    * zone, which corresponds to sp->s_firstdatazone.  To convert a value
  204.    * between the bit number, 'b', used by alloc_bit() and the zone number, 'z',
  205.    * stored in the inode, use the formula:
  206.    *     z = b + sp->s_firstdatazone - 1
  207.    * Alloc_bit() never returns 0, since this is used for NO_BIT (failure).
  208.    */
  209.   sp =